\documentclass[10pt]{article}
\usepackage{amsmath}
\usepackage{graphicx}

\newcommand{\problem}[1]{\noindent{\sc Problem #1.}}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\complexity}{\noindent{\sc Complexity. }}
\newcommand{\answer}{\noindent{\sc Answer. }}
\newcommand{\given}{\,|\,}
\newcommand{\divides}{\,|\,}

\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}

\problem{343}
Fractional Sequences.

For any positive integer $k$, a finite sequence $\{a_i = x_i/y_i\}$ is defined as
\[
a_1 = \frac{1}{k}, a_i = \frac{x_{i-1}+1}{y_{i-1}-1} \text{ reduced to lowest terms for $i>1$}.
\]
The sequence terminates when $a_i$ reaches some integer $n$ (i.e. when $y_i=1$).

Define $f(k) = n$ to be the last term in a sequence starting with $1/k$. For example, for $k = 20$:
\[
\frac{1}{20} \rightarrow \frac{2}{19} \rightarrow \frac{3}{18} = \frac{1}{6}
\rightarrow \frac25 \rightarrow \frac34 \rightarrow \frac43 \rightarrow \frac52 \rightarrow \frac61
\]
So $f(20) = 6$.

Also $f(1) = 1$, $f(2) = 2$, $f(3) = 1$ and $\sum f(k^3) = 118937$ for $1 \le k \le 100$.

Find $\sum f(k^3)$ for $1 \le k \le 2 \times 10^6$.

\solution

Consider the sequence $\{a_i=x_i/y_i\}$ starting from $a_1=1/k$ up to the first term where the fraction can be reduced. We have
\begin{align}
x_i &= i \notag \\
y_i &= k-i+1 \notag
\end{align}
If $x_i / y_i$ can be reduced, then there exists $d>1$ such that $d \divides x_i$ and $d \divides y_i$. It follows that $d \divides i$ and $d \divides k+1$. Since $x_i/y_i$ is the first reducible term, we conclude that $d = i$ and it is the smallest prime factor of $(k+1)$. The reduced fraction is $x'_i=1, y'_i=(k+1)/d-1$.

Thus we find the following recurrence relation for $f(k)$:
\begin{align}
f(k) &= k \text{ if $k+1$ is prime,} \notag \\
f(k) &= f((k+1)/d-1) \text{ otherwise} \notag
\end{align}
where $d$ is the smallest prime factor of $(k+1)$.

The above formula can be greatly simplified by performing a simple variable substitution. Define $g(k)=f(k-1)$ for $k \ge 2$. The recurrence relation for $g(k)$ is
\begin{align}
g(k) &= k-1 \text{ if $k$ is prime,} \notag \\
g(k) &= g(k/d) \text{ otherwise} \notag
\end{align}
where $d$ is the smallest prime factor of $k$. Applying the second equation repeatedly, it is then easy to find that $g(k) = (\text{the largest prime divisor of $k$}) - 1$.

In the context of this problem, we have $f(k^3)=g(k^3+1)$. Note that $k^3+1 = (k+1)(k^2-k+1)$, so the largest prime divisor of $(k^3+1)$ is the larger of the largest prime divisors of $(k+1)$ and $(k^2-k+1)$. We employ the Sieve method to find them separately.

To find out the greatest prime factor of each $(k+1)$ for $1 \le k \le K$, let $u_k=k+1$ be the terms to factorize. Start with $u_1=2$. For each $k$, if $p=u_k$ is prime, we write down $p$ as the largest prime factor of each $u_{k+lp}$ for $0 \le l \le \lfloor (K-k)/p \rfloor$. Continue this process until $k=K$.

To find out the greatest prime factor of each $(k^2-k+1)$ for $1 \le k \le K$, let $v_k = k^2-k+1$ be the terms to factorize. To employ the Sieve method, we need to find out the smallest $v_k$ that contains a given prime factor $p$. 

Suppose that $k_1 < k_2$, and $p$ divides both $v_{k_1}$ and $v_{k_2}$. Then we have
\[
k_1^2 - k_1 + 1 \equiv k_2^2 - k_2 + 1 \text{  (mod $p$)}
\]
It follows that
\[
(k_2-k_1)(k_2+k_1-1) \equiv 0 \text{  (mod $p$)}
\]
A sufficient condition is $k_2 \equiv k_1$ (mod $p$).

Start from $v_1=1$, and update the sequence $\{v_k\}$. For each $k$, if $p=v_k>1$, then we eliminate $p$ from every $v_{k+lp}$ for $1 \le l \le \lfloor (K-k)/p \rfloor$. Continue until $k=K$.

The correctness of the algorithm is shown as follows. When we come to $v'_k$, we have already updated all elements before it according to the rules above. We assert that no prime $p<k$ divides $v'_k$, because such $p$ would also divide $v_{k-p}$ and therefore would have been eliminated from $v_k$. It is obvious that $p=k$ does not divide $v_k$. This means $v'_k$ only contains factors $p > k$. However, such $p^2>v_k \ge v'_k$, therefore $v'_k$ itself is prime.

\answer
269533451410884183

\complexity

Time complexity: $\mathcal{O}(n \log n)$ (guess)

Space complexity: $\mathcal{O}(n)$

\end{document}
